package q1135_minimumCost;

import CommonClass.UF;

import java.util.Arrays;
import java.util.Comparator;

public class Solution_1 {
    /*
    最小生成树的经典例题
    这里用的是并查集和Kruskal结合的方式
    按照不同城市之间连接的权值进行排序
    然后按顺序判断当前的两个城市是否已经连接 如果没有 则ans加入权值
    相当于一种贪心的算法
     */
    public int minimumCost(int n, int[][] connections) {

        // 从1开始的
        UF uf = new UF(n + 1);
        Arrays.sort(connections, Comparator.comparingInt(a -> a[2]));
        // 权重
        int mst = 0;
        for (int[] c : connections) {
            int u = c[0];
            int v = c[1];
            int weight = c[2];
            if (!uf.isConnected(u, v)) {
                mst += weight;
                uf.union(u, v);
            }
        }
        return uf.count() == 2 ? mst : -1;
    }
}
